{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最多牌组数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxGroupNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多牌组数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "麻将的游戏规则中，共有两种方式凑成「一组牌」：\n",
    "- 顺子：三张牌面数字连续的麻将，例如 [4,5,6]\n",
    "- 刻子：三张牌面数字相同的麻将，例如 [10,10,10]\n",
    "\n",
    "给定若干数字作为麻将牌的数值（记作一维数组 `tiles`），请返回所给 `tiles` 最多可组成的牌组数。\n",
    "\n",
    "注意：凑成牌组时，每张牌仅能使用一次。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`tiles = [2,2,2,3,4]`\n",
    ">\n",
    ">输出：`1`\n",
    ">\n",
    ">解释：最多可以组合出 [2,2,2] 或者 [2,3,4] 其中一组牌。\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`tiles = [2,2,2,3,4,1,3]`\n",
    ">\n",
    ">输出：`2`\n",
    ">\n",
    ">解释：最多可以组合出 [1,2,3] 与 [2,3,4] 两组牌。\n",
    "\n",
    "**提示：**\n",
    "- `1 <= tiles.length <= 10^5`\n",
    "- `1 <= tiles[i] <= 10^9`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Up5XYM](https://leetcode.cn/problems/Up5XYM/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Up5XYM](https://leetcode.cn/problems/Up5XYM/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,2,3,4]', '[2,2,2,3,4,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "        tiles = Counter(tiles)\n",
    "        nums = sorted(tiles)\n",
    "        # dp滚动更新，存储的是num的上一个数last_num组成的结尾为last_num+1和结尾为last_num+2的顺子数\n",
    "        dp = {(0, 0): 0}\n",
    "        # nums中有断层，或者，假如没有num+2，也就是num+1为最大值的时候,动态规划更新d是否正确？\n",
    "        # 因为当num遍历到最大值（断层）时，v1必然是0，那么所有大于0的d1都不会出现在最后一轮的d的循环中;\n",
    "        # 满足条件的只有d1=0的情况，而d1=0的循环中，d也必然是0,新的dp只有(0,0)是有值的,也就是之前d0的分配所组成的最大值;\n",
    "        # 这也符合实际的逻辑，如果没有tiles里面num+1，那就无法构成num-1,num,num+1的顺子和num,num+1,num+2的顺子\n",
    "        for num in nums:\n",
    "            v0, v1 = tiles[num], tiles[num+1]\n",
    "            new_dp = Counter()\n",
    "            # 枚举用num-2,num-1,num 和 num-1,num,num+1能组成的顺子中,num和num+1的使用情况\n",
    "            for (d0, d1), c in dp.items():\n",
    "                # 枚举所有num和num+1已经使用的情况\n",
    "                t0, t1 = v0 - d0, v1 - d1\n",
    "                for d in range(min(t0, t1, 2) + 1):\n",
    "                    # num+1变为下一个num,num+1使用情况为:原来使用的 d1 + 当前组成新的顺子使用的 d\n",
    "                    # num+2要使用掉 d\n",
    "                    k = (d1 + d, d)\n",
    "                    # 动态规划, k的使用情况的最大结果为 原来凑成的顺子数 + 新凑出的顺子数 + 剩余num可以组成的刻子数\n",
    "                    # 到这里所有num能使用的情况已经枚举完毕，剩余的num必然是按刻子分\n",
    "                    # 当前num的使用： \n",
    "                    # 组成d0-d1个num-2,num-1,num的顺子，\n",
    "                    # 组成d1个num-1,num,num+1的顺子，\n",
    "                    # 组成d个num,num+1,num+2个顺子\n",
    "                    new_dp[k] = max(new_dp[k], c + d + (t0 - d) // 3)\n",
    "            dp = new_dp\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "        tiles = Counter(tiles)\n",
    "        nums = sorted(tiles)\n",
    "        dp = {(0, 0): 0}\n",
    "        for num in nums:\n",
    "            v0, v1 = tiles[num], tiles[num+1]\n",
    "            new_dp = Counter()\n",
    "            for (d0, d1), c in dp.items():\n",
    "                t0, t1 = v0 - d0, v1 - d1\n",
    "                for d in range(min(t0, t1, 2) + 1):\n",
    "                    k = (d1 + d, d)\n",
    "                    new_dp[k] = max(new_dp[k], c + d + (t0 - d) // 3)\n",
    "            dp = new_dp\n",
    "        return max(dp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "排序后，按顺序遍历tiles中的值，滚动更新顺子的使用数组凑成的最大值。\n",
    "'''\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "        tiles = Counter(tiles)\n",
    "        nums = sorted(tiles)\n",
    "        # dp滚动更新，存储的是num的上一个数last_num组成的结尾为last_num+1和结尾为last_num+2的顺子数\n",
    "        dp = {(0, 0): 0}\n",
    "        # nums中有断层，或者，假如没有num+2，也就是num+1为最大值的时候,动态规划更新d是否正确？\n",
    "        # 因为当num遍历到最大值（断层）时，v1必然是0，那么所有大于0的d1都不会出现在最后一轮的d的循环中;\n",
    "        # 满足条件的只有d1=0的情况，而d1=0的循环中，d也必然是0,新的dp只有(0,0)是有值的,也就是之前d0的分配所组成的最大值;\n",
    "        # 这也符合实际的逻辑，如果没有tiles里面num+1，那就无法构成num-1,num,num+1的顺子和num,num+1,num+2的顺子\n",
    "        for num in nums:\n",
    "            v0, v1 = tiles[num], tiles[num+1]\n",
    "            new_dp = Counter()\n",
    "            # 枚举用num-2,num-1,num 和 num-1,num,num+1能组成的顺子中,num和num+1的使用情况\n",
    "            for (d0, d1), c in dp.items():\n",
    "                # 枚举所有num和num+1已经使用的情况\n",
    "                t0, t1 = v0 - d0, v1 - d1\n",
    "                for d in range(min(t0, t1, 2) + 1):\n",
    "                    # num+1变为下一个num,num+1使用情况为:原来使用的 d1 + 当前组成新的顺子使用的 d\n",
    "                    # num+2要使用掉 d\n",
    "                    k = (d1 + d, d)\n",
    "                    # 动态规划, k的使用情况的最大结果为 原来凑成的顺子数 + 新凑出的顺子数 + 剩余num可以组成的刻子数\n",
    "                    # 到这里所有num能使用的情况已经枚举完毕，剩余的num必然是按刻子分\n",
    "                    # 当前num的使用： \n",
    "                    # 组成d0-d1个num-2,num-1,num的顺子，\n",
    "                    # 组成d1个num-1,num,num+1的顺子，\n",
    "                    # 组成d个num,num+1,num+2个顺子\n",
    "                    new_dp[k] = max(new_dp[k], c + d + (t0 - d) // 3)\n",
    "            dp = new_dp\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "        m = Counter(tiles)\n",
    "        dp = {(0,0):0}\n",
    "        for num in sorted(m):\n",
    "            x,y,z=m[num],m[num+1],m[num+2]\n",
    "            new_dp = collections.defaultdict(int)\n",
    "            for (i,j),c in dp.items():\n",
    "                for k in range(3):\n",
    "                    if i+k<=x and j+k<=y and k<=z:\n",
    "                        new_dp[j+k,k]=max(new_dp[j+k,k],c+(x-i-k)//3+k)\n",
    "            dp=new_dp\n",
    "        return max(dp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "        #copy tourist\n",
    "        curd = [[-inf]*3 for _ in range(3)]\n",
    "        curd[0][0] = 0\n",
    "        prvk = -1\n",
    "        for k,freq in sorted(Counter(tiles).items()):\n",
    "            prvd = curd \n",
    "            curd = [[-inf]*3 for _ in range(3)]\n",
    "            if prvk + 1 ==k:\n",
    "                for beg,med,end in product(range(3),repeat=3):\n",
    "                    if  beg + med + end <= freq:\n",
    "                        curd[beg][med] = max(curd[beg][med],prvd[med][end]+end + (freq-beg-med -end)//3)\n",
    "            else:\n",
    "                for beg in range(min(freq,2)+1):\n",
    "                    curd[beg][0] = prvd[0][0]+(freq-beg)//3\n",
    "            prvk = k\n",
    "        return curd[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles):\n",
    "        K = 5\n",
    "        cnt = defaultdict(int)\n",
    "        \n",
    "        for tile in tiles:\n",
    "            cnt[tile] += 1\n",
    "\n",
    "        dp = [[-1 for _ in range(K)] for _ in range(K)]\n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        last = 0\n",
    "        \n",
    "        for tile, freq in sorted(cnt.items()):\n",
    "            if last != tile - 1:\n",
    "                hi = dp[0][0]\n",
    "                dp = [[-1 for _ in range(K)] for _ in range(K)]\n",
    "                dp[0][0] = hi\n",
    "                \n",
    "            ndp = [[-1 for _ in range(K)] for _ in range(K)]\n",
    "\n",
    "            for i in range(K):\n",
    "                for j in range(K):\n",
    "                    if dp[i][j] < 0:\n",
    "                        continue\n",
    "                    \n",
    "                    # 凑多少个顺子\n",
    "                    for k in range(min(i, min(j, freq)) + 1):\n",
    "                        ni = j - k\n",
    "                        \n",
    "                        # Ensure ni is in range\n",
    "                        if ni < 0 or ni >= K:\n",
    "                            continue\n",
    "                        \n",
    "                        # 当前点数留几张给后面用\n",
    "                        for nj in range(min(K - 1, freq - k) + 1):  # Adjusted the range of nj\n",
    "                            if nj < 0 or nj >= K:  # Check for nj as well\n",
    "                                continue\n",
    "                            ndp[ni][nj] = max(ndp[ni][nj], dp[i][j] + k + (freq - k - nj) // 3)\n",
    "\n",
    "            dp = ndp\n",
    "            last = tile\n",
    "\n",
    "        return max(max(row) for row in dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "\n",
    "        count = collections.defaultdict(int)\n",
    "        for x in tiles:\n",
    "            count[x] += 1\n",
    "        \n",
    "        key_list = sorted([x for x in count])\n",
    "        \n",
    "        dp = [[-1]*5 for _ in range(5)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        prev_tile = 0\n",
    "\n",
    "   \n",
    "        for tile in key_list:\n",
    "            cnt = count[tile]\n",
    "            if prev_tile!=tile-1:\n",
    "                dp00 = dp[0][0]\n",
    "                dp = [[-1]*5 for _ in range(5)]\n",
    "                dp[0][0] = dp00\n",
    "\n",
    "            new_dp = [[-1]*5 for _ in range(5)]\n",
    "\n",
    "            for cnt_2 in range(5):\n",
    "                for cnt_1 in range(5):\n",
    "                    if dp[cnt_2][cnt_1]<0:\n",
    "                        continue \n",
    "                    for shunzi in range(min([cnt_1,cnt_2,cnt ]  )+1 ):\n",
    "                        new_2 = cnt_1-shunzi\n",
    "                        for new_1 in range(min(4, cnt-shunzi)+1):\n",
    "                            new_score =dp[cnt_2][cnt_1]+shunzi+(cnt-shunzi-new_1)//3\n",
    "                            new_dp[new_2][new_1] = max(new_dp[new_2][new_1],new_score)\n",
    "            \n",
    "            dp = [x[:] for x in new_dp]\n",
    "            prev_tile = tile\n",
    "\n",
    "        ans = 0\n",
    "        for cnt_2 in range(5):\n",
    "            for cnt_1 in range(5):\n",
    "                ans = max(ans,dp[cnt_2][cnt_1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "    \n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 7\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "        cc = Counter(tiles)\n",
    "        ans = 0\n",
    "        a = [[int(2e9), 0]]\n",
    "        for x in cc:\n",
    "            while cc[x] >= M:\n",
    "                cc[x] -= 3\n",
    "                ans += 1\n",
    "            a.append([x, cc[x]])\n",
    "        p = -1\n",
    "        f = [[-inf] * M for _ in range(M)]\n",
    "        f[0][0] = 0\n",
    "        for x, y in sorted(a):\n",
    "            if x != p + 1:\n",
    "                t = 0\n",
    "                for i in range(M):\n",
    "                    for j in range(M):\n",
    "                        t = max(t, f[i][j] + i // 3 + j // 3)\n",
    "                ans += t\n",
    "                f = [[-inf] * M for _ in range(M)]\n",
    "                f[0][0] = 0\n",
    "            f2 = [[-inf] * M for _ in range(M)]\n",
    "            f2[0][0] = 0\n",
    "            for i in range(M):\n",
    "                for j in range(M):\n",
    "                    for k in range(y + 1):\n",
    "                        t = min(i, j, k)\n",
    "                        f2[j - t][y - t] = max(f2[j - t][y - t], f[i][j] + (i - t) // 3 + t)\n",
    "            f = f2\n",
    "            p = x\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "        lst = sorted([k, v] for k, v in Counter(tiles).items())\n",
    "        dp = Counter()\n",
    "        if len(lst) == 1:\n",
    "            return lst[0][1] // 3\n",
    "        v0, v1 = lst[0][1], lst[1][1]\n",
    "        for i in range(3):\n",
    "            for j in range(5):\n",
    "                if v0 >= i and v1 >= j:\n",
    "                    dp[(i, j)] = (v0 - i) // 3 + (v1 - j) // 3\n",
    "        for index in range(2, len(lst)):\n",
    "            k, v = lst[index]\n",
    "            new_dp = Counter()\n",
    "            flag = (k - 1 == lst[index - 1][0] and k - 2 == lst[index - 2][0])\n",
    "            for i in range(3):\n",
    "                for j in range(5):\n",
    "                    if v < j:\n",
    "                        continue\n",
    "                    for (pre_i, pre_j), count in dp.items():\n",
    "                        if pre_j >= i:\n",
    "                            c1, c2, c3 = pre_i, pre_j - i, v - j\n",
    "                            c = min(c1, c2, c3) if flag else 0\n",
    "                            new_dp[(i, j)] = max(new_dp[(i, j)], count + c + (c3 - c) // 3)\n",
    "            dp = new_dp\n",
    "        return max(dp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles: List[int]) -> int:\n",
    "        lst = sorted([k, v] for k, v in Counter(tiles).items())\n",
    "        dp = Counter()\n",
    "        if len(lst) == 1:\n",
    "            return lst[0][1] // 3\n",
    "        v0, v1 = lst[0][1], lst[1][1]\n",
    "        for i in range(5):\n",
    "            for j in range(5):\n",
    "                if v0 >= i and v1 >= j:\n",
    "                    dp[(i, j)] = (v0 - i) // 3 + (v1 - j) // 3\n",
    "        for index in range(2, len(lst)):\n",
    "            k, v = lst[index]\n",
    "            new_dp = Counter()\n",
    "            flag = (k - 1 == lst[index - 1][0] and k - 2 == lst[index - 2][0])\n",
    "            for i in range(5):\n",
    "                for j in range(5):\n",
    "                    if v < j:\n",
    "                        continue\n",
    "                    for (pre_i, pre_j), count in dp.items():\n",
    "                        if pre_j >= i:\n",
    "                            c1, c2, c3 = pre_i, pre_j - i, v - j\n",
    "                            c = min(c1, c2, c3) if flag else 0\n",
    "                            new_dp[(i, j)] = max(new_dp[(i, j)], count + c + (c3 - c) // 3)\n",
    "            dp = new_dp\n",
    "        return max(dp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGroupNumber(self, tiles) -> int:\n",
    "        tiles.extend([10**9+3, 10**9+6]) #加两个绝对组不成牌照的牌，避免越界检查\n",
    "        c = Counter(tiles)\n",
    "        t = sorted(c.keys())\n",
    "        res = [[[0]*3 for _ in range(3)] for _ in range(len(t))]\n",
    "\n",
    "        for i in range(len(t)-3, -1, -1) :\n",
    "            for k in range(3) : #以i+1为结尾的顺子有k个\n",
    "                b = c[t[i+1]] - k\n",
    "                if b < 0 : continue\n",
    "                for j in range(3) : #以i为结尾的顺子有j个\n",
    "                    a = c[t[i]] - k - j\n",
    "                    if a < 0 : continue\n",
    "\n",
    "                    res[i][j][k] = a // 3 + res[i+1][k][0]  #以i+2为结尾的顺子为0个\n",
    "                    if t[i]+1 != t[i+1] or t[i+1]+1 != t[i+2] : continue   #无法组成以i+2为结尾的顺子\n",
    "\n",
    "                    for s in range(1, 3) :  #以i+2为结尾的顺子为s个\n",
    "                        if s <= a and s <= b and s <= c[t[i+2]] :\n",
    "                            res[i][j][k] = max(res[i][j][k], (a-s) // 3 + s + res[i+1][k][s])\n",
    "\n",
    "        return res[0][0][0]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
